package main.Q501_600;

import java.util.*;

public class Q501_510 {
    public static void main(String[] args) {
        System.out.println("Question501：二叉搜索树中的众数");
        System.out.println("Question502：");
        System.out.println("Question503：下一个更大的元素Ⅱ");
        System.out.println("Question504：七进制数");
        System.out.println("Question505：");
        System.out.println("Question506：相对名次");
        System.out.println("Question507：完美数");
        System.out.println("Question508：出现次数最多的子树元素和");
        System.out.println("Question509：斐波那契数");
        System.out.println("Question510：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question501{
    public int[] findMode(TreeNode root) {
        Map<Integer,Integer> map=new HashMap<>();
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        if (root==null) return null;
        stack.add(root);
        int maxCount=1;
        while (!stack.isEmpty()){
            TreeNode curNode=stack.pop();
            if (map.containsKey(curNode.val)) {
                map.put(curNode.val,map.get(curNode.val)+1);
                if (map.get(curNode.val)>maxCount) maxCount=map.get(curNode.val);//个数最大
            }
            else map.put(curNode.val, 1);//新加元素
            if (curNode.right!=null) stack.push(curNode.right);
            if (curNode.left!=null) stack.push(curNode.left);
        }
        for (Integer key: map.keySet()) {
            if (map.get(key)==maxCount) list.add(key);
        }
        int[] result=new int[list.size()];
        for (int i=0;i<list.size();i++) result[i]=list.get(i);
        return result;
    }
}

class Question503{
    public int[] nextGreaterElements(int[] nums) {
        int length= nums.length;
        int[] result=new int[length];
        Arrays.fill(result,-1);
        Stack<Integer> stack=new Stack<>();
        for (int i=0;i<2*length;i++){
            while (!stack.isEmpty()&&nums[i%length]>nums[stack.peek()]){
                result[stack.pop()]=nums[i%length];
            }
            stack.push(i%length);
        }
        return result;
    }
}

class Question504{
    public String convertToBase7(int num) {
        String result;
        if (num<0){
            num=-1*num;
            result="-"+Integer.toUnsignedString(num,7);
        }else result=Integer.toUnsignedString(num,7);
        return result;
    }
}

class Question506{
    public String[] findRelativeRanks(int[] score) {
        String[] answer=new String[score.length];
        for (int i=1;i<=score.length;i++){//按顺序生成名次
            if (i==1) answer[0]="Gold Medal";
            else if (i==2) answer[1]="Silver Medal";
            else if (i==3) answer[2]="Bronze Medal";
            else answer[i-1]=Integer.toString(i);
        }
        for (int i=0;i<score.length-1;i++){//根据成绩将名次逆排序
            for (int j=0;j<score.length-i;j++){
                if (score[j]<score[j+1]) {
                    String temp=answer[j];
                    answer[j]=answer[j+1];
                    answer[j+1]=temp;
                }
            }
        }
        return answer;
    }
}

class Question507{
    public boolean checkPerfectNumber(int num) {
        int sum=1;
        for (int i=2;i<=(int)Math.sqrt(num);i++){
            if (num%i==0) sum=sum+i+num/i;
        }
        if (num==1) return false;
        if (sum==num) return true;
        else return false;
    }
}

class Question508{
    Map<Integer,Integer> map=new HashMap<>();
    int maxCount=0;
    public Integer process(TreeNode root){
        if (root==null) return null;
        Integer left=process(root.left);//左子树和
        Integer right=process(root.right);//右子树和
        int sum=root.val;
        if (left==null&&right==null) {
            map.put(sum,map.getOrDefault(sum,0)+1);
            maxCount=Math.max(maxCount,map.get(sum));
        }
        else if (left==null&&right!=null) {
            sum+=right;
            map.put(sum,map.getOrDefault(sum,0)+1);
            maxCount=Math.max(maxCount,map.get(sum));
        }
        else if ((left!=null&&right==null)) {
            sum+=left;
            map.put(sum,map.getOrDefault(sum,0)+1);
            maxCount=Math.max(maxCount,map.get(sum));
        }
        else {
            sum=sum+left+right;
            map.put(sum,map.getOrDefault(sum,0)+1);
            maxCount=Math.max(maxCount,map.get(sum));
        }
        return sum;
    }
    public int[] findFrequentTreeSum(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        process(root);
        for (Integer integer:map.keySet()){
            if (map.get(integer)==maxCount)
                list.add(integer);
        }
        int[] arr=new int[list.size()];
        for (int i=0;i<list.size();i++) arr[i]=list.get(i);
        return arr;
    }
}

class Question509{
    public int fib(int n) {
        int head=0,end=1,result=1;
        for (int i=2;i<=n;i++){
            result=head+end;
            head=end;
            end=result;
        }
        if (n==0) result=0;
        else if (n==1) result=1;
        return result;
    }
}